#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 100;
const int maxn = 16;

int n;
struct Node {
    int to, w;
};
vector<Node> adj[maxn];
int f[1 << maxn][maxn]; // f[s][now] 状态 s，当前走到 now 的最小距离

/*
    f[s | (1 << to)][to] = min(self, f[s][now] + adj[now][to]);
*/

int main() {
    memset(f, inf, sizeof(f));
    n = rad();
    for (int i = 0, ed = n * (n + 1); i < ed; ++i) {
        int l = rad(), r = rad(), w = rad();
        adj[l].push_back({r, w});
    }

    int ed = (1 << n + 1) - 1;
    f[1][0] = 0;
    for (int s = 1; s < ed; ++s) {
        for (int now = 0; now <= n; ++now) {
            if ((s & (1 << now)) == 0) continue; // illegal
            for (auto &p : adj[now]) {
                int s2 = s | (1 << p.to);
                if (s2 != s)
                    f[s2][p.to] = min(f[s2][p.to], f[s][now] + p.w);
            }
        }
    }
    int ans = inf;
    for (int now = 1; now <= n; ++now) {
        for (auto &p : adj[now])
            if (p.to == 0)
                ans = min(ans, f[ed][now] + p.w);
    }
    printf("%d", ans);
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}